/*************************************************************************
 * File Name:    LRU_Cache.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/18 11:26:43
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: LRU Cache
 | Design and implement a data structure for Least Recently Used (LRU) cache.
 | It should support the following operations: get and set.
 |
 | get(key) - Get the value (will always be positive) of the key if the key exists in the cache,
 | otherwise return -1.
 |
 | set(key, value) - Set or insert the value if the key is not already present.
 | When the cache reached its capacity, it should invalidate the least recently
 | used item before inserting a new item.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <list>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class LRUCache{
public:
    LRUCache(int capacity)
    {
        this->capacity = capacity;
    }
    
    int get(int key)
    {
        if (cache.find(key) == cache.end()) return -1;
        list<pair<int,int> >::iterator it = cache[key];
        key_value.push_front(*it);
        key_value.erase(it);
        cache[key] = key_value.begin();
        
        return key_value.front().second;
    }
    
    void set(int key, int value)
    {
        if (cache.find(key) != cache.end()) {
            list<pair<int,int> >::iterator it = cache[key];
            it->second = value;
            key_value.push_front(*it);
            key_value.erase(it);
            cache[key] = key_value.begin();
        } else if (key_value.size() < capacity) {
            key_value.push_front(pair<int,int>(key,value));
            cache[key] = key_value.begin();
        } else {
            key_value.push_front(pair<int,int>(key,value));
            cache[key] = key_value.begin();
            cache.erase(key_value.back().first);
            key_value.pop_back();
        }
    }

private:
    int capacity;
    
    //pair<key,value>
    list<pair<int,int> > key_value;
    
    map<int, list<pair<int,int> >::iterator> cache;
};

int
main(int argc, char *argv[])
{
    LRUCache run = LRUCache(2);

    run.set(2,1);
    run.set(2,2);
    cout << run.get(2) << endl;
    run.set(1,1);
    run.set(4,1);
    cout << run.get(2) << endl;

    return 0;
}
